package com.chenyi.data.structure.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

/**
 * @author by chenyi
 * @className ReversePolishNotation
 * @date 2022/1/17 15:09
 */

public class ReversePolishNotation {

    public static String getReversePolishNotation(String expression) {
        List<String> chars = stringChar(expression.toCharArray());

        Stack<String> middleStack = new Stack<>();
        Stack<String> reversePolishNotationStack = new Stack<>();

        for (int i = 0; i < chars.size(); i++) {
            if (!CalculatorStack.isOperator(chars.get(i)) && CalculatorStack.isBrackets(chars.get(i)) == -1) {
                StringBuilder builder = new StringBuilder();
                builder.append(chars.get(i));
                // 循环添加数字，用于判断当前数字是否是多位数
                for (int j = i + 1; j < chars.size(); j++) {
                    if (!CalculatorStack.isOperator(chars.get(j)) && CalculatorStack.isBrackets(chars.get(j)) == -1) {
                        builder.append(chars.get(j));
                        i++;
                    } else {
                        break;
                    }
                }
                reversePolishNotationStack.push(builder.toString());
            } else if (CalculatorStack.isBrackets(chars.get(i)) == -1) {
                // 运算符添加操作
                while (true) {
                    // 如果s1为空那么就直接添加，或者栈顶运算符为'('时也直接添加
                    if (middleStack.isEmpty() || CalculatorStack.isBrackets(middleStack.peek()) == 0) {
                        middleStack.push(chars.get(i));
                        break;
                    } else if (CalculatorStack.operatorSize(middleStack.peek()) < CalculatorStack.operatorSize(chars.get(i))) {
                        // 若当前运算符优先级比栈顶的运算符高直接添加到栈中
                        middleStack.push(chars.get(i));
                        break;
                    } else {
                        // 如果middleStack栈顶的运算符高于当前运算符
                        // 那么将middleStack栈顶运算符弹出压入到reversePolishNotationStack中
                        // 再次判断运算符等级
                        String operator = middleStack.pop();
                        reversePolishNotationStack.push(operator);
                    }
                }
            }
            // 判断是否为左括号
            if (CalculatorStack.isBrackets(chars.get(i)) == 0) {
                middleStack.push(chars.get(i));
            } else if (CalculatorStack.isBrackets(chars.get(i)) == 1) {
                // 判断是为右括号后依次弹出middleStack栈顶的运算符存入到reversePolishNotationStack直到遇到左括号位置，此时将这一对括号丢弃
                while (true) {
                    String operator = null;
                    if (!middleStack.isEmpty()) {
                        operator = middleStack.pop();
                        // 遇到左括号将这对括号丢弃
                        if (CalculatorStack.isBrackets(operator) == 0) {
                            String leftBrackets = middleStack.pop();
                            leftBrackets = null;
                            break;
                        } else {
                            reversePolishNotationStack.push(operator);
                        }
                    } else {
                        break;
                    }
                }
            }
        }

        // 将middleStack中的运算符依次弹出放入reversePolishNotationStack
        while (!middleStack.isEmpty()) {
            String operator = middleStack.pop();
            reversePolishNotationStack.push(operator);
        }

        // 将reversePolishNotationStack中的元素依次弹出结果的逆序就是对应的后缀表达式
        StringBuilder builder = new StringBuilder();
        for (String s : reversePolishNotationStack) {
            builder.append(s);
            builder.append(",");
        }

        return builder.toString();
    }

    public static List<String> stringChar(char[] chars) {
        List<String> strings = new ArrayList<>();
        for (char aChar : chars) {
            strings.add(String.valueOf(aChar));
        }
        return strings;
    }

    public static int reversePolishNotationCalculator(String reversePolishNotation) {
        String[] strings = reversePolishNotation.split(",");

        Stack<Integer> result = new Stack<>();

        for (String item : strings) {
            // 判断是否是数字
            if (item.matches("\\d+")) {
                result.push(Integer.parseInt(item));
            } else {
                // 是符号就pop出两个数进行运算
                Integer num1 = result.pop();
                Integer num2 = result.pop();
                int calculate = CalculatorStack.calculate(num1, num2, item.charAt(0));
                result.push(calculate);
            }
        }

        return result.peek();
    }

}
